package DoExercise.HSP_ZCY.A008_树.A001_普通二叉树.二叉树递归套路_找可能性;

import java.util.ArrayList;


/**
 * 给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的头节点
 *
 * 返回谁的节点数更多，不是值更大
 *
 *           61
 *         41  91
 *       2   5 81 101
 *     1  3
 * 上面树返回2 ，91是3个点，2也是三个点，优先左树
 *
 *           61
 *         41  91
 *       2   5 81 101
 *     1  3   71 90
 * 上面返回 91 因为91有5个
 *
 */
public class Code05_最大二叉搜索子树的头节点
{
    
    
    public static void main(String[] args)
    {
        
        Node root1 = new Node(61);
        Node root2 = new Node(41);
        Node root3 = new Node(91);
        Node root4 = new Node(2);
        Node root5 = new Node(5);
        Node root6 = new Node(1);
        Node root7 = new Node(3);
        Node root8 = new Node(81);
        Node root9 = new Node(101);
        Node root10 = new Node(71);
        Node root11 = new Node(90);
        
        root1.left = root2;
        root1.right = root3;
        root2.left = root4;
        root2.right = root5;
        root3.left = root8;
        root3.right = root9;
        root4.left = root6;
        root4.right = root7;
        root8.left = root10;
        root8.right = root11;
    
        System.out.println(maxSubBSTHead1(root1).value);
        System.out.println(maxSubBSTHead2(root1).value);
    
        //        int maxLevel = 4;
        //        int maxValue = 100;
        //        int testTimes = 1000000;
        //        for (int i = 0; i < testTimes; i++)
        //        {
        //            Node head = generateRandomBST(maxLevel, maxValue);
        //            if (maxSubBSTHead1(head) != maxSubBSTHead2(head))
        //            {
        //                System.out.println("Oops!");
        //            }
        //        }
        //        System.out.println("finish!");
    }
    
    
    public static class Node
    {
        public int value;
        public Node left;
        public Node right;
        
        public Node(int data)
        {
            this.value = data;
        }
    }
    
    public static int getBSTSize(Node head)
    {
        if (head == null) return 0;
        ArrayList<Node> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++)
        {
            if (arr.get(i).value <= arr.get(i - 1).value)
            {
                return 0;
            }
        }
        return arr.size();
    }
    
    public static void in(Node head, ArrayList<Node> arr)
    {
        if (head == null)
        {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }
    
    public static Node maxSubBSTHead1(Node head)
    {
        if (head == null)
        {
            return null;
        }
        if (getBSTSize(head) != 0)
        {
            return head;
        }
        Node leftAns = maxSubBSTHead1(head.left);
        Node rightAns = maxSubBSTHead1(head.right);
        return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
    }
    
    public static Node maxSubBSTHead2(Node head)
    {
        if (head == null)
        {
            return null;
        }
        return process(head).maxSubBSTHead;
    }
    
    public static class Info
    {
        public Node maxSubBSTHead;//最大二叉搜索子树的头节点
        public int maxSubBSTSize;//最大二叉搜索子树的大小
        public int min;
        public int max;
        
        public Info(Node h, int size, int mi, int ma)
        {
            maxSubBSTHead = h;
            maxSubBSTSize = size;
            min = mi;
            max = ma;
        }
    }
    
    public static Info process(Node head)
    {
        if (head == null)
        {
            return null;
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int min = head.value;
        int max = head.value;
        Node maxSubBSTHead = null;
        int maxSubBSTSize = 0;
        if (leftInfo != null)
        {
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
            maxSubBSTHead = leftInfo.maxSubBSTHead;
            maxSubBSTSize = leftInfo.maxSubBSTSize;
        }
        if (rightInfo != null)
        {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
            if (rightInfo.maxSubBSTSize > maxSubBSTSize)
            {
                maxSubBSTHead = rightInfo.maxSubBSTHead;
                maxSubBSTSize = rightInfo.maxSubBSTSize;
            }
        }
        //leftInfo.maxSubBSTHead == head.left 如果左树的最大头节点的值就是当前节点左树的值，那么就认为head.left是一个BST
        if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == head.left && leftInfo.max < head.value)) && (rightInfo == null ? true : (rightInfo.maxSubBSTHead == head.right && rightInfo.min > head.value)))
        {
            maxSubBSTHead = head;
            maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize) + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
        }
        return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
    }
    
    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue)
    {
        return generate(1, maxLevel, maxValue);
    }
    
    // for test
    public static Node generate(int level, int maxLevel, int maxValue)
    {
        if (level > maxLevel || Math.random() < 0.5)
        {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }
    
    
}
